#include "utilities.h"

Utilities::Utilities()
{
}

Utilities::~Utilities()
{
}

int Utilities::bmpSearch(const std::string &text, const std::string &pattern,vector<int> bmpLast)
{
    size_t textSize = text.size();
    size_t patternSize = pattern.size();
    if(textSize == 0 || patternSize == 0){
        return -1;
    }
    if(patternSize > textSize){
        return -1;
    }

    //vector<int> bmpLast = computeBmpLast(pattern);
    size_t tIdx = patternSize - 1;
    size_t pIdx = patternSize - 1;
    while(tIdx < textSize){
        if(pattern[pIdx] == text[tIdx]){
            if(pIdx == 0){   //found a match
                return tIdx;
            }
            tIdx--;
            pIdx--;
        }
        else {
            //Character Jump Heuristics
            int lastOccur = bmpLast[text[tIdx]];
            tIdx = tIdx + patternSize - min<int>(pIdx, 1 + lastOccur);
            pIdx = patternSize - 1;
        }
    }
    return - 1;
}

vector<int> Utilities::computeBmpLast(const std::string &pattern)
{
    const size_t NUM_ASCII_CHARS = 128;
    vector<int> bmpLast(NUM_ASCII_CHARS);
    for(size_t i = 0; i < NUM_ASCII_CHARS; i++){
        bmpLast[i] = -1;
    }
    for(size_t i = 0; i < pattern.size(); i++){
        bmpLast[pattern[i]] = i;
    }
    return bmpLast;
}

string Utilities::convertInfixPostfix(StringTokenizer tokenizer)
{
	int openParenthesisEncountered = 0;
	//int closedParenthesisEncountered = 0;
	string previousToken="";
	string currentToken="";
	string postfixNotationString = "";
	//perform validation of expression
	queue<string> infixNotationQueue;
	while (true)
	{
		currentToken = tokenizer.nextToken();
		if (matcher.matchExact(currentToken,""))
		{
			//error sudden end of file encountered
			break;
		}
		if (matcher.matchExact(previousToken,""))
		{
			//first item to be handled
			if (matcher.matchConstValue(currentToken)
				||matcher.matchVarName(currentToken))

			{
				infixNotationQueue.push(currentToken);
			}
			else if (matcher.matchExact(currentToken,"("))
			{
				openParenthesisEncountered++;
				infixNotationQueue.push(currentToken);
			}
			else
			{
				//invalid tokens encountered
				return "error";
			}
		}
		else
		{
			//subsequent items to be handled
			if (matcher.matchExact(currentToken,"("))
			{
				//handle token (
				if (matcher.matchExact(previousToken,"(")||matcher.matchOperator(previousToken))
				{
					infixNotationQueue.push(currentToken);
					openParenthesisEncountered++;
				}
				else
				{
					//error msg

					return "error";
				}


			}
			else if (matcher.matchExact(currentToken,")"))
			{
				//handle token )
				if (openParenthesisEncountered<=0)
				{
					return "error";
				}
				else if (matcher.matchVarName(previousToken)||matcher.matchExact(previousToken,")")||matcher.matchConstValue(previousToken))
				{
					infixNotationQueue.push(currentToken);
					openParenthesisEncountered--;
				}
				else
				{
					return "error";
				}
			}
			else if (matcher.matchOperator(currentToken))
			{
				//handle token + - * /
				if (matcher.matchConstValue(previousToken)||matcher.matchVarName(previousToken)||matcher.matchExact(previousToken,")"))
				{
					infixNotationQueue.push(currentToken);
				}
				else
				{

					return "error";
				}
			}
			else if (matcher.matchConstValue(currentToken)||matcher.matchVarName(currentToken))
			{
				//handle constant or variables
				if (matcher.matchOperator(previousToken)||matcher.matchExact(previousToken,"("))
				{
					infixNotationQueue.push(currentToken);
				}
				else
				{
					return "error";
				}
			}
			else
			{
				//invalid token encountered
				return "error";
			}
		}
		previousToken=currentToken;
	}

	//check if the parenthesis is done properly
	if (openParenthesisEncountered!=0)
	{
		return "error";
	}

	//perform shunting yard algorithm
	
	stack<string> shuntingYardStack;
	queue<string> postfixNotationQueue;

	while (!infixNotationQueue.empty())
	{
		string shunting_temp = infixNotationQueue.front();
		infixNotationQueue.pop();
		if (matcher.matchConstValue(shunting_temp)||matcher.matchVarName(shunting_temp))
		{
			//const or varName encountered
			postfixNotationQueue.push(shunting_temp);
		}
		else if (matcher.matchOperator(shunting_temp))
		{
			//operator encountered
			while (!shuntingYardStack.empty())
			{
				if (matcher.getOperatorPrecedence(shunting_temp)<=matcher.getOperatorPrecedence(shuntingYardStack.top()))
				{
					postfixNotationQueue.push(shuntingYardStack.top());
					shuntingYardStack.pop();
				}
				else
				{
					break;
				}
			}
			shuntingYardStack.push(shunting_temp);
			
		}
		else if (matcher.matchExact(shunting_temp,"("))
		{
			// ( encountered
			shuntingYardStack.push(shunting_temp);
		}
		else if (matcher.matchExact(shunting_temp,")"))
		{
			// ) encountered
			//pop all operators onto postfixNotationQueue, until we find the (
			while (!matcher.matchExact(shuntingYardStack.top(),"("))
			{
				postfixNotationQueue.push(shuntingYardStack.top());
				shuntingYardStack.pop();
			}
			//finally pop the (
			shuntingYardStack.pop();
		}
	}
	while (!shuntingYardStack.empty())
	{
		postfixNotationQueue.push(shuntingYardStack.top());
		shuntingYardStack.pop();
	}

	//convert postfix notation to AST
	while (!postfixNotationQueue.empty())
	{
		if (postfixNotationString.length()==0)
		{
			postfixNotationString+=postfixNotationQueue.front();
		}
		else
		{
			postfixNotationString +=",";
			postfixNotationString +=postfixNotationQueue.front();
		}
		postfixNotationQueue.pop();
	}
	string finalPostfixNotationString = ","+postfixNotationString+",";
	return finalPostfixNotationString;
}